package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author qidi
 * @date 2022-01-04 14:12:07
 */
class Q0103_BinaryTreeZigzagLevelOrderTraversal {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;

            Deque<TreeNode> q = new ArrayDeque<>();
            Deque<TreeNode> next = new ArrayDeque<>();
            q.add(root);
            List<Integer> inner = new ArrayList<>();

            boolean flag = true;
            while (!q.isEmpty()) {
                TreeNode node = q.pop();
                inner.add(node.val);
                if (node.left != null) next.add(node.left);
                if (node.right != null) next.add(node.right);

                if (q.isEmpty()) {
                    if (flag) {
                        result.add(new ArrayList<>(inner));
                        flag = !flag;
                    } else {
                        List<Integer> in = new ArrayList<>();
                        for (int i = inner.size() - 1; i >= 0; i--) {
                            in.add(inner.get(i));
                        }
                        result.add(in);
                        flag = !flag;
                    }
                    inner.clear();
                    q.addAll(next);
                    next.clear();
                }
            }

            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0103_BinaryTreeZigzagLevelOrderTraversal().new Solution();
    }
}